/**
 * Created by zhangjinrui on 17/6/27.
 */

public class Solution105 {

    public static void main(String args[]){
        Solution105 s = new Solution105();
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return dfs(preorder, inorder);
    }

    public TreeNode dfs(int[] pre, int[] in){
        if(pre.length == 0){
            return null;
        }
        if(pre.length == 1){
            return new TreeNode(pre[0]);
        }
        int v = pre[0];
        int split = 0;
        for(int i = 0 ; i < in.length ; i ++){
            if(in[i] == v){
                split = i;
                break;
            }
        }

        TreeNode cur = new TreeNode(v);
        int[] preL = new int[split];
        int[] inL = new int[split];
        for(int i = 0 ; i < split; i ++){
            preL[i] = pre[i + 1];
            inL[i] = in[i];
        }

        int[] preR = new int[pre.length - split - 1];
        int[] inR = new int[pre.length - split - 1];
        for(int i = 0; i < pre.length - split - 1;  i++){
            preR[i] = pre[split + i + 1];
            inR[i] = in[split + 1 + i];
        }
        cur.left = dfs(preL, inL);
        cur.right = dfs(preR, inR);
        return cur;
    }

}
